1. Field of the Invention
This invention relates to a method of efficient encoding which can reduce the total number of bits of recorded or transmitted data. This invention also relates to a method of related decoding. In addition, this invention relates to apparatus for efficient encoding and decoding.
2. Description of the Prior Art
Highly-efficient encoding is of various types, and some of encoding is based on the combination of two of the types. Systems for efficiently encoding image data and audio data are being standardized. The standardization of a system for efficiently encoding still image data is advanced by JPEG, a lower branch of International Standardization Organization (ISO), and is now nearly completed.
A description will now be given of a prior-art JPEG efficient encoding of the DCT (discrete cosine transform) type which is disclosed in "Draft (Version 6) of the JPEG algorithm", JPEG-8-R6, Jun. 24, 1990.
Input data is digital image data, that is, a sampled and quantized image signal. A frame represented by the image data is divided into blocks each having 8 by 8 pixels (8 pixels in a horizontal direction, and 8 pixels in a vertical direction), and the image data is rearranged into sets of data which correspond to the blocks respectively. This process is referred to as "blocking". The image data in each block is subjected to 8-degree discrete cosine transform (referred to as DCT hereinafter), generating a set of DCT coefficients corresponding to the image data. A set of DCT coefficients has one DC coefficient and 63 AC coefficients. Each DCT coefficient is quantized with a given quantization step size Q. In other words, each DCT coefficient is divided by Q, and the result of the division is rounded. The resultant quantized AC coefficients are two-dimensionally encoded into a Huffman code. The resultant quantized DC coefficient is predictively encoded.
The predictive encoding of a quantized DC coefficient will be described hereinafter. A quantized DC coefficient is represented by data Di (i=1, 2, 3, . . . , and "i" denotes an order number of data which is equal to an order number of a related block). In the predictive encoding, an estimate (a prediction value) Pi is calculated from input data Dk which is previously encoded, and an estimation error (a prediction error) Si equal to the difference between the data Di and the estimate Pi is calculated and then the estimation error Si is encoded. Here, the letter "k" denotes an integer smaller than the integer "i". This prediction is of the 0-th order type and is executed on the basis of a previous value, and the immediately-preceding input data is used as the estimate.
The encoding of an estimation error (a prediction error) Si will be described hereinafter. One of preset categories identified by different numbers (category indexes) is selected in accordance with the value of an estimation error Si, and the identification number (the category index) corresponding to the selected category is encoded into a Huffman code. The category index corresponds to the information represented by higher bits of the estimation error. Lower bits of the estimation error are cut and taken out. The number L of these lower bits is determined by the category index. The lower bits of the estimation error are outputted subsequently to the category-index Huffman code. In this way, the estimation error is divided into higher-bit information and lower-bit information, and each of the higher-bit information and the lower-bit information is encoded. If L lower bits of an estimation error (a prediction error) are directly cut and taken out, duplicated code words occur in a positive side and a negative side respectively. Accordingly, in cases where an estimation error is negative, "1" is subtracted from the estimation error and then L lower bits of the result of the subtraction are cut and taken out.
According to a variable-length encoding procedure such as a Huffman encoding procedure, short code words are assigned to data having high probabilities of occurrence while long code words are assigned to data having small probabilities of occurrence, so that the total number of bits of generated code words can be reduced in time average. The variable-length encoding is highly efficient, and is reversible.
In image data and audio data, adjacent data are closely correlated so that an estimation error is close to "0" at a high probability. Thus, advanced highly-efficient encoding is enabled by assigning short code words to identification numbers (category indexes) for categories corresponding to estimation errors having small absolute values.
Such predictive encoding (one of highly-efficient encoding) has a problem as follows. A decoding side recovers decoded values through processes including a process of integrating or accumulating the estimation-error data outputted from an encoding side. Thus, if an error occurs in the signal transmitted from the encoding side to the decoding side due to noise or others, the affection by the error is accumulated and remains in the decoding side for a long time so that the propagation of the error is caused.
U.S. Pat. No. 5,034,965 discloses highly-efficient encoding in which data processing is executed block by block. In general, a large-scale circuit is required to implement such block-by-block data processing.
Variable-length encoding such as Huffman encoding is inherently efficient. In general variable-length encoding, input data is encoded into variable-length code words, and the data store region in a transmission format is stuffed with a bit sequence composed of the code words before data transmission is executed. FIG. 8 shows an example of the arrangement of variable-length code words in the data store region in a prior-art transmission format. As shown in FIG. 8, "n" variable-code words Ci (i=1, 2, 3, . . . , n) are sequentially arranged in the data store region, and there is no open space between adjacent code words. In addition, the first code C1 extends from the starting edge of the data store region, and the last code word Cn is spaced from the ending edge of the data store region by an open area.
According to such variable-length encoding and related decoding, if an error occurs in the transmission of code words from an encoding side to a decoding side, the lengths of code words following the error can not be detected and also the boundaries between the code words following the error can not be detected. Thus, in the presence of an error, the code words following the error can not be accurately decoded. This problem is referred to as error propagation (see C. Yamamitsu, et al, "AN EXPERIMENTAL STUDY FOR A HOME-USE DIGITAL VTR", IEEE Trans. CE-35, No. 3, Aug. 1989, pp 450-457).